
// 279.完全平方数
class Solution {
public:
    int numSquares(int n) {
        // 使用完全背包来完成
        const int INF = 0x3f3f3f3f;
        vector<int> dp(n + 1 , INF);
        dp[0] = 0;
        for(int i = 1 ; i*i <= n ; i++)
        {
            // 当前选择的数是 i*i
            int number = i*i;
            for(int j = number; j <= n ;j++)
            {
                // 还需要使用一个循环 , 向前面找 , 看选择number几次
                dp[j] = min(dp[j] , dp[j - number] + 1);
            }
        }        
        return dp[n];
    }
};